package com.str.map;
public class LinkedMap implements Map {

  // Each LinkedMap object is a map in which the keys are Comparable
  // objects and the values are arbitrary objects.

  // This map is represented as follows: its cardinality is held in card;
  // first is a link to the first node of a SLL containing the entries.

// Inner class
  private static class Entry {
    // Each ArrayMap.Entry object is a map entry consisting of a key,
    // which is a Comparable object, a value, which is an arbitrary
    // object, and a link to the next entry in the SLL.
    Object key;
    Object value;
    Entry next;

    Entry(Object k, Object v, Entry n) {
      key = k;
      value = v;
      next = n;
    }
    	
    public String toString()
    { return "<" + key + "," + value + ">";	}
  }
  
  private Entry first;
  private int count;

// Constructor
  public LinkedMap() {
  // Construct a map, initially empty.
    clear();
  }

// Modifiers
  public final void clear() {
  // Make this map empty.
    first = null;
	count = 0;
  }

  public void add(Object key, Object val) {	
  	Entry ref = search(key);
    if (ref == null) {		
	  first = new Entry(key, val, first);	  
	  count++;
	}
  }

  public Object remove(Object key) {
    Entry prior = null, curr = first;
  	while (curr != null) {
   	  if (key.equals(curr.key)) {
	    Object temp = curr;  	  		
	    if (prior == null)
		  first = curr.next;
        else  
		  prior.next = curr.next;		    
	    count--;
	    return temp;
	  }
      prior = curr;
	  curr = curr.next; 
	}
	return null;
  }

// Accessors
  public boolean isEmpty() {
    // Return true if and only if this map is empty.
	return count == 0;
  }

  public int size() {
  // Return this maps size.
	return count;
  }
    
  public Object getValue(Object key) {
    // Return the value in the entry with key in this map, or null if there
    Entry ref = search(key);
    if (ref != null) return ref.value;
	else return null;	
  }
  
// Auxiliary methods
  private Entry search(Object key) {
	for (Entry curr = first; curr != null; curr = curr.next)
	  if (key.equals(curr.key))
	    return curr;
    return null;
  }
 
  public String toString() {
    String buf = "{ ";
    for (Entry curr = first; curr != null; curr = curr.next) {
      if (curr != first) buf += ", ";
      buf += curr;
    }
    buf += " }";
    return buf;
  }
}

